package main

import "fmt"

// 归并排序
// 归并排序是一种分治策略的排序算法。它是一种比较特殊的排序算法，通过递归地先使每个子序列有序，再将两个有序的序列进行合并成一个有序的序列

// MergeSort 自顶向下的归并排序递归实现，排序范围再 [begin int, end int)的数组
func MergeSort(array []int, begin int, end int) {
	// 元素数量 > 1才进入递归拆分
	if end - begin > 1 {
		// 将数组一分为二，分为array[begin, mid) 和 [mid, high)
		mid := begin + (end - begin + 1) / 2

		// 递归排序左边
		MergeSort(array, begin, mid)

		// 递归排序右边
		MergeSort(array, mid, end)

		// 将已经排好序的左右两个有序数组进行合操作
		merge(array, begin, mid, end)
	}
}

// MergeSort2 自底向上的归并排序实现
// 自底向上非递归排序，我们可以看到没有递归那样程序栈的增加，效率比自顶向下的递归版本高
func MergeSort2(array []int, begin, end int) {
	// 步长从1开始，step长度的数组表示一个有序的数组
	step := 1

	// 范围大于step 的数组才可以进入归并
	for end - begin > step {
		// 从头到尾对数组进行归并操作
		for i := begin; i < end; i += step << 1 {
			var lo = i				// 第一个有序数组的左边界
			var mid = lo + step  	// 第一个有序数组的右边界，第二个有序数组的左边界
			var hi = lo + (step << 1)  // 第二个有序数组的右边界

			// 不存在第二个数组，直接返回
			if mid > end {
				return
			}
			// 第二个数组的长度不够
			if hi > end {
				hi = end
			}

			// 合并两个有序数组
			merge(array, lo, mid, hi)
		}

		// 上一个循环中step长度的两个数组均归并成为一个数组了，现在步长翻倍
		step <<= 1
	}
}


// 归并操作
func merge(array []int, begin int, mid int, end int) {
	// 申请额外的空间来合并两个有序数组，这两个数组是array[begin, mid), array[mid, end)
	leftSize := mid - begin 	// 左边数组的长度
	rightSize := end - mid		// 右边数组的长度
	newSize := leftSize + rightSize // 辅助数组的长度
	temp := make([]int, 0, newSize)

	l, r := 0, 0
	for l < leftSize && r < rightSize {
		lValue := array[begin + l]  // 左边数组的元素
		rValue := array[mid + r]    // 右边数组的元素
		// 小的元素放到辅助数组中
		if lValue < rValue {
			temp = append(temp, lValue)
			l++
		} else {
			temp = append(temp, rValue)
			r++
		}
	}

	// 将剩下的元素追加到辅助数组后面
	temp = append(temp, array[begin + l: mid]...)
	temp = append(temp, array[mid + r: end]...)

	// 将辅助数组的元素复制回原数组，这样该辅助空间就可以被释放掉
	for i := 0; i < newSize; i++ {
		array[begin + i] = temp[i]
	}
	return
}


func main() {

	list := []int{5}
	MergeSort2(list, 0, len(list))
	fmt.Println(list)
	list1 := []int{5, 9}
	MergeSort2(list1, 0, len(list1))
	fmt.Println(list1)
	list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	MergeSort2(list2, 0, len(list2))
	fmt.Println(list2)
}































